#include <GameEngine/Maps/hex_map.h>

#include <GameEngine/Maps/map_cell.h>
#include <GameEngine/Core/Memory/memory_manager.h>
#include <GameEngine/Geometry/Surfaces/hexagon2d.h>

#include <math.h>
#include <vector>
#include <iostream>


#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=====================================================================

Q_DECLARE_OPERATORS_FOR_FLAGS(HexMap::Connectivity)

//=====================================================================


//! Constructor
/*!
 @param width The width of the hexagonal map
 @param height The height of the hexagonal map
 */
HexMap::HexMap(MapSize width, MapSize height) :
	cells_(nil), Map(width,height)
{
	// Allocate cell array
	MapSize sz = width * height;
	if ( sz > 0 ) cells_ = MemoryManager::instance()->allocate<Cell>(sz);
}

//! Destructor
HexMap::~HexMap() {
	MemoryManager::instance()->desallocate(cells_,width_*height_);
}

//! Compute the index of the cell from the location of one of its points
/*!
 @param index Receives the index of the cell, if this cells exists
 @param rhs The location of a point that belongs to the cell
 @return True if a cell containing the given point exists, false otherwise
 */
bool HexMap::get_cell_index(CellIndex& index, const Point2d<float>& rhs) const {
	// Convert to cell coordinates and return cell
	MapIndex x = 0, y = 0;
	if ( get_map_indexes(x,y,rhs) == false ) return false;
	return get_cell_index(index,x,y);
}

//! Compute the index of the cell from the (x,y) indexes along the grid
/*!
 @param index Receives the index of the cell, if this cells exists
 @param x The x index of the cell
 @param y The y index of the cell
 @return True if a cell with given (x,y) indexes exists, false otherwise
 */
bool HexMap::get_cell_index(CellIndex& index, MapIndex x, MapIndex y) const {
	if ( x >= width_ ) return false;
	if ( y >= height_ ) return false;
	index = get_array_index(x,y);
	return true;
}

//! Compute the map indexes of the cell from the location of one of its points
/*!
 @param x Receives the x index of the cell, if this cells exists
 @param y Receives the y index of the cell, if this cells exists
 @param rhs The location of a point that belongs to the cell
 @return True if a cell containing the given point exists, false otherwise
 */
bool HexMap::get_map_indexes(MapIndex& x, MapIndex& y, const Point2d<float>& rhs) const {
	// Convert point to local coordinates
	Point2d<float> local = global_to_local_coordinates(rhs);
	if ( ( local.x() < 0 ) || ( local.y() < 0 ) || ( local.x() > 1 ) || ( local.y() > 1 ) ) return false;

	// Convert x to cell coordinates
	MapIndex xtmp = (MapIndex)(local.x() * (float)width_);
	if ( xtmp >= width_ ) xtmp = width_-1;

	// Convert y to cell coordinates
	MapIndex ytmp = (MapIndex)(local.y() * (1+2*height_));
	if ( ytmp >= (1+2*height_) ) ytmp = 2*height_;

	// Get all possible cells
	std::vector< std::pair<int,int> > possible_cells;
	possible_cells.push_back( std::pair<int,int>(xtmp-1,ytmp/2) );
	possible_cells.push_back( std::pair<int,int>(xtmp,ytmp/2) );
	possible_cells.push_back( std::pair<int,int>(xtmp+1,ytmp/2) );
	if ( ( ytmp % 2 ) == 0 ) {
		for ( int k = 0; k < 3; ++k ) {
			std::pair<int,int> pair = possible_cells[k];
			pair.second -= 1;
			possible_cells.push_back( pair );
		}
	}

	// Test possible cells
	Vector2d<float> orientation(0,1.0f/(float)(1+2*height_));
	for ( std::vector< std::pair<int,int> >::iterator it = possible_cells.begin(); it != possible_cells.end(); ++it ) {
		// Get hexagon center
		Point2d<float> center = Point2d<float>(
			(float)( 1+2*it->first ) / (float)( 2*width_ ),
			(float)( (it->first % 2) + 1 + 2*it->second ) / (float)( 1+2*height_ )
		);

		// Get hexagon
		Hexagon2d<float> hex( center, orientation );
		if ( hex.inside(local) == false ) continue;
		x = it->first;
		y = it->second;
		return true;
	}
	return false;
}

//! Get the cell of the map at given location, if any
/*!
 @param rhs The location where a cell should be found, specified in world coordinates
 @return A pointer to the cell (may be nil if the map does not have any cell at given location)
 */
HexMap::Cell* HexMap::get_cell(const Point2d<float>& rhs) const {
	// Get map coordinates
	MapIndex x, y;
	if ( get_map_indexes(x,y,rhs) == false ) return nil;

	// Convert to cell coordinates and return cell
	return get_cell(x,y);
}

//! Accessor to one of the cells of the map
/*!
 @param x The index of the cell along the width axis
 @param y The index of the cell along the height axis
 @return A pointer to the cell (may be nil if the map does not have any cell at given index)
 */
HexMap::Cell* HexMap::get_cell(MapIndex x, MapIndex y) const {
	if ( x >= width_ ) return nil;
	if ( y >= height_ ) return nil;
	return get_cell( get_array_index(x,y) );
}

//! Accessor to one of the cells of the map
/*!
 @param index The index of the cell in the cell array
 @return A pointer to the cell (may be nil if the map does not have any cell at given index)
 */
HexMap::Cell* HexMap::get_cell(CellIndex index) const {
	if ( index >= (width_*height_) ) return nil;
	return (cells_+index);
}

//! Compute the geometry of the cell at given map coordinates, if any
/*!
 @param x The x map coordinate where a cell should be found
 @param y The y map coordinate where a cell should be found
 @return The geometry of the cell, if any
 */
std::vector< Point2d<float> > HexMap::get_cell_geometry(MapIndex x, MapIndex y) const {
	// Build corresponding hexagon
	Vector2d<float> orientation(2.0/(float)(sqrt(3.0)*(1+2*height_)),0);
	float xval = (float)( 1+2*x ) / (float)( 2*width_ );
	float yval = (float)( (x % 2) + 1 + 2*y ) / (float)( 1+2*height_ );
	Point2d<float> center = map_box_.point( Coords2d<float>(xval,yval) );
	Hexagon2d<float> hex( center, orientation );

	// Put the six cell points in the result vector and return result
	std::vector< Point2d<float> > res;
	float ratio = map_box_.v2().length() / map_box_.v1().length();
	for ( int k = 0; k < 6; ++k ) {
		Vector2d<float> vec(center,hex[(Hexagon2D::Index)k]);
		vec.x() /= ratio * 2.0 * sqrt(3.0) * ( (float)height_ / ( (float)width_ + 1 ) );
		res.push_back( Point2d<float>(center.x()+vec.x(),center.y()+vec.y()) );
	}
	return res;
}

//! Compute the geometry of the cell at given location, if any
/*!
 @param rhs The location where a cell should be found, specified in world coordinates
 @return The geometry of the cell, if any
 */
std::vector< Point2d<float> > HexMap::get_cell_geometry(const Point2d<float>& rhs) const {
	std::vector< Point2d<float> > res;

	// Get the map indexes of the cell
	MapIndex x = 0, y = 0;
	if ( get_map_indexes(x,y,rhs) == false ) return res;

	// Build corresponding hexagon
	return get_cell_geometry(x,y);
}

//=================================================================================

//! Constructor
/*!
 @param map The map that defines the space of research
 @param displacement_types The types of displacement allowed on the map
 */
HexMapSearch::HexMapSearch(const HexMap& map, const Displacement::DisplacementTypes& displacement_types) :
	map_(map), displacement_types_(displacement_types) {}

//! Desctructor
HexMapSearch::~HexMapSearch() {}

//! Compute the list of all cells adjacent to the input index
/*!
 @param children The list of all cells adjacent to the input index
 @param node The node whose adjacent cells should be found
 @return Always return true
 */
bool HexMapSearch::get_children(std::list<Node>& children, Node node) const {
	// Get the node indexes
	Map::MapIndex x = 0, y = 0;
	map_.get_axes_indexes(x, y, node);

	// Populate the list
	long x_offset[] = { 1,-1, 0, 0, 1, 1};
	long y_offset[] = { 0, 0, 1,-1, 1,-1};
	if ( ( y % 2 ) == 0 ) {
		x_offset[4] *= -1;
		x_offset[5] *= -1;
	}
	for ( int k = 0; k < 6; ++k ) {
		// If cell does not exist, do nothing
		HexMap::Cell* cell = map_.get_cell(x+x_offset[k], y+y_offset[k]);
		if ( cell == nil ) continue;

		// If the cell is not walkable, do not add it
		if ( map_.terrains().get_terrain(cell->terrain()).speed(displacement_types_) <= 0 ) continue;

		// Add the cell to the list
		Map::CellIndex index = map_.get_array_index(x+x_offset[k], y+y_offset[k]);
		children.push_back( index );
	}

	// Return result
	return true;
}

//! Compute the cost to go from the parent to the current node
/*!
 @param parent The parent of the current node
 @param node The current node
 @return The cost to go from the parent to the current node
 */
HexMapSearch::Cost HexMapSearch::cost(Node parent, Node node) const {
	// Get map coordinates
	Map::MapIndex xp, yp, xn, yn;
	map_.get_axes_indexes(xp,yp,parent);
	map_.get_axes_indexes(xn,yn,node);

	// Get parent center
	float xpval = (float)( 1+2*xp ) / (float)( 2*map_.width_ );
	float ypval = (float)( (xp % 2) + 1 + 2*yp ) / (float)( 1+2*map_.height_ );
	Point2d<float> centerp = map_.map_box_.point( Coords2d<float>(xpval,ypval) );

	// Get node center
	float xnval = (float)( 1+2*xn ) / (float)( 2*map_.width_ );
	float ynval = (float)( (xn % 2) + 1 + 2*yn ) / (float)( 1+2*map_.height_ );
	Point2d<float> centern = map_.map_box_.point( Coords2d<float>(xnval,ynval) );

	// Compute the cost as the average of both costs
	return centerp.get_square_distance(centern);
}

//=================================================================================

//! Constructor
/*!
 @param map The map that defines the space of research
 */
HexMapSearchHeuristic::HexMapSearchHeuristic(const HexMap& map) : map_(map) {}

//! Desctructor
HexMapSearchHeuristic::~HexMapSearchHeuristic() {}

//! Compute the cost to go from the parent to the current node
/*!
 *  Cost is estimated as the euclidean distance between the nodes
 *
 @param start The current node
 @param end The node to get to
 @return The estimated cost to go from the current to the end node
 @note This function implicitly assumes that the speed of displacement is 1 all over the map
 */
HexMapSearch::Cost HexMapSearchHeuristic::cost(HexMapSearch::Node start, HexMapSearch::Node end) const {
	// Get map coordinates
	Map::MapIndex xs, ys, xe, ye;
	map_.get_axes_indexes(xs,ys,start);
	map_.get_axes_indexes(xe,ye,end);

	// Get parent center
	float xsval = (float)( 1+2*xs ) / (float)( 2*map_.width_ );
	float ysval = (float)( (xs % 2) + 1 + 2*ys ) / (float)( 1+2*map_.height_ );
	Point2d<float> centers = map_.map_box_.point( Coords2d<float>(xsval,ysval) );

	// Get node center
	float xeval = (float)( 1+2*xe ) / (float)( 2*map_.width_ );
	float yeval = (float)( (xe % 2) + 1 + 2*ye ) / (float)( 1+2*map_.height_ );
	Point2d<float> centere = map_.map_box_.point( Coords2d<float>(xeval,yeval) );

	// Compute the cost as the average of both costs
	return centere.get_square_distance(centers);
}



#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif
